Imosu Act (fifth highest of the eight hereditary titles, later demoted to sixth highest of eight)
Add the same value to a range of arrays
$ A_i ← A_i + X[s \le i < e] where s: start, e: end
This query is done Q times
O(NQ) when implemented naively.
Add only the beginning and end of the range first.
$ B_i ← B_i + X[i = s] - X[i=e]
$ A_i ← A_{i-1} + B_i
It's like calculating in derivative form and then integrating at the end.
cumulative sum algorithm extended to multi-dimensional and multi-order ---
This page is auto-translated from /nishio/いもす法. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.